/**
 * //给定一个包含红色、白色和蓝色、共 n 个元素的数组
 * // nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 * //
 * // 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
 * //
 * //
 * //
 * //
 * // 必须在不使用库的sort函数的情况下解决这个问题。
 * //
 * //
 * //
 * // 示例 1：
 * //
 * //
 * //输入：nums = [2,0,2,1,1,0]
 * //输出：[0,0,1,1,2,2]
 * //
 * //
 * // 示例 2：
 * //
 * //
 * //输入：nums = [2,0,1]
 * //输出：[0,1,2]
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // n == nums.length
 * // 1 <= n <= 300
 * // nums[i] 为 0、1 或 2
 * //
 * //
 * //
 * //
 * // 进阶：
 * //
 * //
 * // 你可以不使用代码库中的排序函数来解决这道题吗？
 * // 你能想出一个仅使用常数空间的一趟扫描算法吗？
 * //
 * //
 * // Related Topics 数组 双指针 排序 👍 1387 👎 0
 */

package com.xixi.basicAlgroithms.dualPointer;

public class ID00075SortColors {
    public static void main(String[] args) {

        Solution solution = new ID00075SortColors().new Solution();
        solution.sortColors(new int[]{2, 0, 2, 1, 1, 0});
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void sortColors(int[] nums) {

            int red = -1;
            int white = -1;
            int b = 0;

            while (b < nums.length) {
                if (nums[b] == 0) { //扫到红的，
                    // 先换到红的下一个位置， 有可能是，第一个白的位置
                    swap(++red, b, nums);
                    white++;
                    //如果换过去的是个白色
                    if (nums[b] == 1) {
                        //得换到白色最后一个来
                        swap(white, b, nums);
                    }

                } else if (nums[b] == 1) { //扫到白的
                    //直接换到白色后面
                    swap(white + 1, b, nums);
                    white++;
                }
                b++;

            }


        }

        public void swap(int a, int b, int[] nums) {
            int tmp = nums[a];
            nums[a] = nums[b];
            nums[b] = tmp;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}